package com.chj.gaoji.class14;

import java.util.TreeMap;

public class Code03_CountofRangeSum {

//	作者：acw_weian
//	链接：https://leetcode-cn.com/problems/count-of-range-sum/solution/327-qu-jian-he-de-ge-shu-chi-san-hua-shu-zhuang-sh/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//    if(nums ==  null || nums.length == 0){
//        return 0;
//    }
//    //键值为区间和和这个区间和出现的次数
//    TreeMap<Long, Integer> treeMap = new TreeMap<>();
//    treeMap.put(0L, 1);
//    
//    int count = 0;
//    long sum = 0L;
//    for(int num : nums){
//        sum += num;
//        //subMap()返回一个值在sum - upper 和sum - lower 之间的子集合，values()方法获得这个键值对中值的集合
//        for(int cnt : treeMap.subMap(sum - upper, true, sum - lower, true).values()){
//            count += cnt; //统计满足条件的区间和个数
//        }
//        treeMap.put(sum, treeMap.getOrDefault(sum, 0) + 1);
//    }
//    return count;
//
//作者：jinnzenn
//链接：https://leetcode-cn.com/problems/count-of-range-sum/solution/java-treemapde-jie-fa-shou-xie-shu-zhuang-shu-zu-t/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//	https://www.1point3acres.com/bbs/thread-165074-1-1.html

	public static int countRangeSumRand(int[] nums, int lower, int upper) {
		if (nums == null || nums.length <= 0) {
			return 0;
		}

		long[] sum = new long[nums.length];
		sum[0] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			sum[i] = sum[i - 1] + nums[i];
		}

		int total = 0;
		TreeMap<Long, Integer> treeMap = new TreeMap<>();
		for (int i = 0; i < nums.length; i++) {
			// [0,i]区间之和在所给区间范围内
			if (sum[i] >= lower && sum[i] <= upper) {
				total++;
			}

			// sum[i] - x >= lower && sum[i] - x <= upper 即 sum[i] - upper <= x <=sum[i] -
			// lower
			// 这个x代表的是sum[j],其中j<i。上面的式子表达的是[j+1, i]区间和在[lower,upper]之间。
			for (Integer count : treeMap.subMap(sum[i] - upper, true, sum[i] - lower, true).values()) {
				total += count;
			}
			Integer count = treeMap.get(sum[i]);
			if (count == null) {
				count = 1;
			} else {
				count++;
			}
			treeMap.put(sum[i], count);
		}

		return total;
	}

	public static void main(String[] args) {
		{
			int[] nums = { -2, 5, -1 };
			int lower = -2, upper = 2;

			System.out.println(countRangeSumRand(nums, lower, upper));
			System.out.println(countRangeSumRand(nums, lower, upper));
		}

		{
//			[-2147483647,0,-2147483647,2147483647]
//					-564
//					3864
			int[] nums = { -2147483647, 0, -2147483647, 2147483647 };
			int lower = -564, upper = 3864;

			System.out.println(countRangeSumRand(nums, lower, upper));
			System.out.println(countRangeSumRand(nums, lower, upper));
		}

		{
//			int[] a = { -2, 5, -1 };
//			int lower = -2, upper = 2;
//
//			int N = a.length;
//			Code03_CountofRangeSum cc = new Code03_CountofRangeSum();
//			int[] ans = new int[20];
//			int[] path = new int[20];
//			int sum = 0;
//			int index = 0;
//			int indexp = 0;
//
////			[-4, -2, 0, 1, 2, 3, 4, 5]
//			cc.ys = new ArrayList<>();
//			cc.ys.add((long) -4);
//			cc.ys.add((long) -2);
//			cc.ys.add((long) 0);
//			cc.ys.add((long) 1);
//			cc.ys.add((long) 2);
//			cc.ys.add((long) 3);
//			cc.ys.add((long) 4);
//			cc.ys.add((long) 5);
//
//			ans[index++] = cc.find(0) + 1;
//			path[indexp++] = 0;
//			for (int i = 0; i < N; i++) {
//				sum += a[i];
//				int ref1 = cc.find(sum - upper) + 1, ref2 = cc.find(sum - lower) + 1;
//				ans[index++] = ref1;
//				ans[index++] = ref2;
//				ans[index++] = cc.find(sum) + 1;
//
//				path[indexp++] = sum - upper;
//				path[indexp++] = sum - lower;
//				path[indexp++] = sum;
//			}
//
//			System.out.println(path);
//			System.out.println(ans);
		}
	}
}
